package Algorithm.Dp;

//https://leetcode-cn.com/problems/house-robber-ii/
//213. 打家劫舍 II
public class Leetcode213_house_robber_ii {
    class Solution {
        public int rob(int[] nums) {
            if(nums.length<2){
                return nums[0];
            }

            int max = 0;
            int[] dp = new int[nums.length];
            dp[0] = nums[0];
            dp[1] = Math.max(dp[0],nums[1]);
            for(int i=2;i<nums.length-1;i++){
                dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
            }

            max = Math.max(max, dp[nums.length-2]);

            dp = new int[nums.length];
            dp[0] = 0;
            dp[1] = Math.max(dp[0],nums[1]);
            for(int i=2;i<nums.length;i++){
                dp[i] = Math.max(dp[i-1],dp[i-2] + nums[i]);
            }

            max = Math.max(max, dp[nums.length-1]);

            return max;

        }
    }
}
